1. Field of the Invention
The present invention relates to the learning technology of a topological map which is employed in, for example, representing a map or chart for navigation of a mobile object adapted to move within an environment (or space), such as a mobile robot.
2. Description of the Related Art
A map or chart needs to be utilized for efficient navigation in, for example, the case where a mobile object moves from a certain position to another. Similarly, in fact, a person utilizes various maps in accordance with such purposes.
An ordinary map, to be used by a person, is formed by measuring such information items as bearings, distances, heights etc. with instruments. Information items, representing geographical features, roads etc. are then described on a medium such as paper with marks, so that many people can share and utilize the map.
On the other hand, each of many organisms, including humans, can acquire a cognitive map (or what is called a "good knowledge of a locality") in their brains, on the basis of learning by moving about within an environment. Whereas the so-called "ordinary map" is for general use by any person, the cognitive map an organism forms by the learning process is for individual use and is purpose-dependent.
In a case where a mobile object can form a map by learning, the following advantages are brought forth:
1) When the mobile object is situated in an unfamiliar environment and is not endowed with any existing map, it can form a map of the environment by learning by itself.
2) When an existing map is unsuitable for a certain purpose, the mobile object can learn a map suitable for this purpose.
3) The mobile object can form a more effective map based on the kinds of available sensors or receptors (by way of example, a map based on vision is useless to a mobile robot which has only an ultrasonic sensor).
Accordingly, it is a very important function that a map can be formed in a self-organized fashion by the learning process.
As regards methods of representing maps, there are ordinary maps (in which bearings, distances, heights etc. are represented in two dimensions by the use of marks), maps which utilize identification trees (or tree structures), maps which are represented using coordinates, and so on. In the present invention, maps or charts are specifically represented by utilizing the topological maps or topology preserving maps proposed by Teuvo Kohnen in the papers "Self-Organized Formation of Topologically Correct Feature Maps, Biological Cybernetics 43, 59-69, 1982", "The Self-Organizing Map, The Proceedings of IEEE, VOL. 78, NO. 9, 1464-1480, 1990", etc. The topological map is one model of a neural network. Neutral network have the feature that a "topology preserving map", in which a mutual similarity (in a phase structure) between input patterns is reflected in the positional relationship of firing neurons, can be formed by learning. Now, the topological map will be explained.
(A) Structure of a Topological Map
A topological map is a neural network which has a single-layer structure as illustrated in FIG. 1. The neural network is configured of N (=N.sub.1 .times.N.sub.2) units (or neurons) which are arranged in two dimensions. It is provided with vectors x.epsilon.R.sup.M as inputs. Here, the letter M denotes the number of dimensions of the inputs. Further, underlined symbols indicate vector quantities in the ensuing explanation. Since the ith unit receives sensor information through a synapse coupling vector (hereinafter, termed a "synaptic weight") w.sub.i .epsilon.R.sup.M (i=1, . . . , N), the input u.sub.i to the unit `i` is computed in accordance with the following equation: ##EQU1##
The outputs y.sub.i (i=1, . . . , N) of the neural network are determined so that, as indicated by the following equations (2) and (3), the unit `c` having received the maximum input becomes a winner. Thus, only the winner unit fires (delivering an output "1 (one)"), whereas the remaining units do not fire (may deliver outputs "0's (zeros)"): EQU c={i:w.sub.i .multidot.x.gtoreq.w.sub.j .multidot.x, for all j}(2) ##EQU2##
When the inputs x and the synaptic weights w.sub.i are normalized to unit vectors, the winner unit can also be determined as the unit `c` which has the synaptic weight w.sub.i closest to (or most resembling) the input x, as indicated by an equation (4) given below. In the following explanation, it will be assumed for the sake of brevity that both the inputs x and the synaptic weights w.sub.i are normalized to be unit vectors. EQU c={i:.parallel.x-w.sub.i .parallel.&lt;.parallel.x-w.sub.j .parallel., for all j } (4)
(B) Learning Rule
In the learning technology of a topological map, learning proceeds through receipt of inputs x corresponding respectively to patterns close to each other in a certain environment or space. When such inputs have been received, units or neurons similarly close to each other on the topological map fire.
In the learning process, the variation .DELTA.w.sub.i of the synaptic weight w.sub.i is computed in accordance with the following equation (5): ##EQU3## Here, symbol .eta. denotes a positive constant for determining the rate of learning, and the symbol L(c) denotes the set of units around the winner unit "c" (or in the vicinity of the winner unit). Eq. (5) indicates that only the synaptic weights w.sub.i of the winner unit "c" satisfying Eq. (4), and the units belonging to the surrounding set L(c), are altered by the learning process. The synaptic weights w.sub.i of the other units are not changed. It is generally considered favorable to set a larger value for the constant .eta. and a wider range for the set L(c) at the initial stage of the learning process, and to gradually decrease the value of the constant .eta. and narrow the range of the set L(c) as the learning process proceeds.
(C) Property and Fields of Application
A learning process based on the learning rule, explained in the item (B) above, enables a topological map having the structure explained in the item (A) above to obtain a map in which the similarity of the inputs x is reflected in the vicinity or closeness of the positions of the firing winner units "c". That is, a map is obtained in which the topology (phase structure) of the inputs is preserved.
Using this property, topological maps have been applied various fields including, for example, the sorting of inputs, motion controls, speech recognition, vector quantization, and combination optimizing problems. The self-organized formation of a map or chart based on learning, toward which the preferred embodiments of the present invention to be described later are directed, is one of the applications of the sorting of the inputs x. More specifically, in each of the preferred embodiments, a topological map serving as a map or chart in which a position within any desired environment or space is specified on the basis of the inputs x from any position detecting sensor, can be realized by utilizing the property that, when the inputs x indicate positions within the space, the individual inputs x corresponding respectively to positions close to each other within the space are mapped as the winner units "c" similarly close to each other on the learnt topological map. This operation is just correspondent to the action of a person in which he/she specifies his/her current position on the basis of visual information obtained by eye.
The learning rule of the topological map in the prior art as explained in the item (B) is assumed on the condition that the inputs (or input vectors) x are selected from within an input space X at random or in accordance with a certain probability distribution. Here, in a case where the information items of the environment or space are measured by sensors while a mobile object is moving within the environment, and where a map or chart is to be formed from the obtained sensor information, the input information items from the sensors are not taken at random, but they are taken along the moving path of the mobile object. Nevertheless, the learning rule in the prior art is general and does not make use of a nature peculiar to the field of application. It is therefore impossible to utilize the fact that the inputs x are taken along the moving path, in other words, motion information.
For this reason, the prior-art learning rule has the problems that the learning constant .eta. and the learning range L(c) needs to be properly regulated in accordance with the number of times of learning, and a long time period is expended on the learning. Further, the prior-art learning rule has the problem that the learning sometimes fails to proceed successfully, so a map or chart based on the formed topological map falls into a so-called "distorted" state.